package binary_tree.leetcode.medium;

import java.util.*;

/**
 * @author bruin_du
 * @description 从上到下打印二叉树 III
 * @date 2022/5/20 16:59
 **/
public class Offer32III_LevelOrder {
    //还可以尝试这三种方法
    //方法一:不改变队列的添加方式,使用LinckedList对奇偶层用不同的插入方式
    //方法二:不需要在单个循环中判断条件,奇偶层的逻辑分离,直接对奇数层处理,然后注意判空,看是否有偶数层,在对偶数层处理
    //奇数层头读,先左后右尾插;偶数层尾读,先右后左头插.注意在一个队列中插入方向不能相同,否则结果不正确
    //方法三:进行奇偶层判断,对List的结果集进行反转,调用Collections.reverse(tmp)
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int level = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            level++;
            List<Integer> childList = new ArrayList<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
            for (int i = 0; i < size; i++) {
                stack.offerLast(queue.poll());
            }
            for (int i = 0; i < size; i++) {
                TreeNode node = stack.pollLast();
                childList.add(node.val);
                if((level & 0x1) == 1){
                    if(node.left != null)
                        queue.offer(node.left);
                    if(node.right != null)
                        queue.offer(node.right);
                }else{
                    if(node.right != null)
                        queue.offer(node.right);
                    if(node.left != null)
                        queue.offer(node.left);
                }
            }
            list.add(childList);
        }
        return list;
    }
}
